#ifndef _FAST_H_
#define _FAST_H_
//#include <vector>
#include "cvt.h"
class TreeNode
{
 public:
  TreeNode ()
    {
      this->count = 1;
      this->left = NULL;
      this->right = NULL;
    }
  int index ;// Point index in the sites;
  //Point cordinate; //Point Cordinate 
  Polygon bound;
  int layer;
  int count;
  TreeNode * left;
  TreeNode * right;
  Polygon & get_boundary (Polygon & boundary)
    {
      boundary = this->bound;
      return boundary;
    }
  Point & get_pos (std::vector <Point> & sites)
  {
    return sites[index];
  }
};
class Hierarchy
{
 public:
  Hierarchy (Polygon & boundary);
  ~Hierarchy ();
  TreeNode * getroot()
  {
    return root; 
  }
  void insert (std::vector<Point> & sites, unsigned i); 
  void hierarchy_tessellation (std::vector<Point> & sites );
  void output_result (std::vector<Point> & v_p);
  void output_cvt ()
  {
  	//Output the result of cvt. 
  }
 public:
  void recursive_refine (std::vector<Point> & sites, TreeNode * node);
  void refine (std::vector<Point> & sites, TreeNode * node);
  void split_bound(Polygon & bound, Polygon & b1, Polygon & b2, int layer);
  //if side = 0, excludes the boundary ,
  // othewise don't
  bool is_in (Polygon & bound, Polygon & adjacent, Point & p, int side)
  {
  	if (side == 0)
  	{
  		if (bound.has_on_boundary(p) && !adjacent.has_on_boundary(p)) return true;
  		else return bound.has_on_bounded_side(p);
	}
	else
	{
		return (bound.has_on_boundary(p)  || bound.has_on_bounded_side(p));
	}
  	/*
	if (side == 0)
    		return bound.has_on_bounded_side(p);
	else 
	{
		return (bound.has_on_boundary(p)  || bound.has_on_bounded_side(p));
	}
	*/
  }
 protected:
  void traverse (TreeNode * its, std::vector<Point> & v_p)
  {
    if (its != NULL)
      {
      	if (its->count == 1)
      	{
	  std::cout<<"Node Index: "<<its->index<<std::endl;
	  std::cout<<"Node Value: "<<v_p[its->index]<<std::endl;
	}
	std::cout<<"Node Layer: "<<its->layer<<std::endl;
	std::cout<<"Node Count: "<<its->count<<std::endl;
	std::cout<<"Node Bound: "<<its->bound<<std::endl;
	std::cout<<std::endl;
	traverse (its->left, v_p);
	traverse (its->right, v_p);
      } 
  }
 protected:
  //void insert_recursive (std::vector<Point> & sites, int index, TreeNode * node);
  void destroy_tree (TreeNode * node);
  std::vector<Point> sites;
  Polygon bound; 
  TreeNode * root; 
  CVT cvt;
};

class LookasideHierarchy: public Hierarchy
{
 public:
  void hierarchy_tessellation (std::vector<Point> & sites );
  void recursive_refine (std::vector<Point> & sites, TreeNode * node, TreeNode * aside, Polygon & bound);
  void refine (std::vector<Point> & sites, TreeNode * node, TreeNode * aside, Polygon & bound);
  void refine (std::vector<Point> & sites, TreeNode * node);
  LookasideHierarchy (Polygon & boundary):Hierarchy (boundary)
  {
//    this->bound = boundary;
//    root = NULL;
  }
};
#endif
